Ở cấp độ cơ bản nhất, một danh sách liên kết là một cấu trúc dữ liệu đệ quy được định nghĩa bởi sự vắng mặt hay thành phần của chính nó. Một danh sách là hoặc rỗng (biểu diễn dưới dạng []) hoặc nó bao gồm một Đầu chứa một giá trị duy nhất và một Đuôi đó chính là một danh sách hoàn chỉnh.

1. Định nghĩa Đệ quy

Bằng cách định nghĩa đuôi là "chính nó là một danh sách", chúng ta cho phép lồng ghép vô hạn. Điều này được minh họa qua việc xây dựng [ 1 | [ 2 | [ 3 | [ ] ] ] ], trong đó mỗi toán tử ống (|) tách biệt giá trị ngay lập tức khỏi cấu trúc còn lại.

2. Nguyên thủy so với Trừu tượng

Danh sách nguyên thủy trong VM Erlang (BEAM) là những cấu trúc đơn giản. Các hành vi như List.flatten/1 là trừu tượng cung cấp bởi module List của Elixir. Cấu trúc dữ liệu thô không "biết" cách dàn phẳng chính nó; module cung cấp logic để duyệt qua các đầu và đuôi lồng nhau.

3. So sánh Với Quả Búp Bê Nga

Hãy hình dung danh sách liên kết giống như một bộ quả búp bê Nga. Quả búp bê bên ngoài cùng là Đầu. Khi bạn mở nó ra, bạn chỉ tìm thấy đúng một thứ: một quả búp bê khác (quả Đuôi). Bạn chỉ đạt đến trạng thái Rỗng khi bạn mở quả búp bê cuối cùng và nhỏ nhất và không tìm thấy gì bên trong.